package com.gitee.alg.sort

/**
 * Project Name: alg
 * Des:归并排序，  从上到下 递归实现，
 * Package:com.gitee.alg.sort
 * @author Arlo Sun
 * @date 2021/4/26 - 22:41
 */
class MergeSort<T : Comparable<T>>(override val compare: (T, T) -> Boolean) : ArraySort<T> {

    override fun sort(array: Array<T>, ascend: Boolean): Array<T> {

        // 即只有一个元素的数组是有序的
        if (array.size < 2) {
            return array
        }

        //右移1位
        val middle = array.size shr 1

        val left = array.copyOfRange(0, middle)
        val right = array.copyOfRange(middle, array.size)

        return merge(sort(left), sort(right))
    }

    private fun merge(left: Array<T>, right: Array<T>): Array<T> {
        val array = left.copyOf().plus(right.copyOf())
        //left的索引
        var li = 0
        //right的索引
        var ri = 0
        //合并后的数组的索引
        var si = 0

        while (li < left.size && ri < right.size) {
            array[si++] = if (compare(left[li], right[ri])) right[ri++] else left[li++]
        }

        while (li < left.size) {
            array[si++] = left[li++]
        }

        while (ri < right.size) {
            array[si++] = right[ri++]
        }

        return array
    }


}
